package com.sourcetrip.algorithm.unionfind;

import com.sourcetrip.algorithm.abs.AbstractUnionFind;

/**
 * @author: ZhouBert
 * @date: 2021/1/5
 * @description: 并查集（以 Quick Union 的思路实现）
 * --
 * 在 V0 上进行优化，避免出现树退化成链表的情况。
 * 于是 V1 版本是基于当前节点的深度进行的优化（但是似乎并不是个很好的方案！）
 * 因为当前深度很可能是冰山一角！
 */
public class UnionFindWithQuickUnionV1 extends AbstractUnionFind {
	/**
	 * 构建固定容量的并查集
	 * 默认初始 parents 的元素的根节点指向自身，这样表示每个元素都是独立的集合
	 *
	 * @param capacity 并查集的容量
	 */
	public UnionFindWithQuickUnionV1(int capacity) {
		super(capacity);
	}

	@Override
	public int find(int v) {
		rangeCheck(v);
		int p = v;
		while (parents[p] != p) {
			p = parents[p];
		}
		return p;
	}


	@Override
	public void union(int v1, int v2) {
		rangeCheck(v1);
		rangeCheck(v2);
		int h1 = 0, h2 = 0;
		int p1 = v1, p2 = v2;
		while (parents[p1] != p1) {
			h1++;
			p1 = parents[p1];
		}
		while (parents[p2] != p2) {
			h2++;
			p2 = parents[p2];
		}
		if (p1 == p2) {
			return;
		}
		//如果 左边的高度大于右边，就将右边依附到左边
		if (h1 > h2) {
			parents[p2] = p1;
		} else {
			parents[p1] = p2;
		}
	}
}
